leetcode 动态规划

动态规划（Dynamic Programming）

Those who cannot remember the past are condemned to repeat it.

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

三个核心元素：最优子结构、边界、状态转移方程式

多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

动态规划一般可分为

线性动规，etc:拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规，etc:石子合并，加分二叉树，统计单词个数，炮兵布阵等；
树形动规，etc:贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包动规。etc:背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶

同类问题通常有三种方式思考
简单递归
备忘录算法（优化时间复杂度）
动态规划（优化时间，空间复杂度）

利用简洁的自底向上的递推方式，实现了时间和空间上的最优化。

缺点局限：

时间复杂度（n*w）空间复杂度（w）当所求单位很多时，需要很多空间。反而不如简单递归（跟w无关）。

LeetCode 选题

菜 53、70、121
中 62、63、322
死 32 、44、174、403

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解：

思路：动态规划最简单的应用，max

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i]= nums[i] + max(nums[i-1], 0)
        return max(nums)

70. 爬楼梯

思路：正常做法，就是最简单的动态规划。省略代码。

看到一个有趣的。做法二：通过设置缓存区，通过递归法运行时间测试。

from functools import lru_cache

class Solution:
    @lru_cache(10**8)   #设置个缓存
    def climbStairs(self, n):
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n - 1) + self.climbStairs(n - 2)

121. 买卖股票的最佳时机

思路：很简单的一道题，需要注意的就是取最低点买入。然后在高点卖出。满足，低点在前，高点在后。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        min_ = prices[0]
        result = 0        
        for i in range(1, len(prices)):
            min_ = min(min_, prices[i])
            result = max(result, prices[i] - min_)
            
        return result

62. 不同路径

思路：

这个题其实可以用排列组合的方式来做。

以模拟的[4, 7]的例子,每一条路径：

向右的肯定有6步;
向左的肯定有3步;

问题即为:c(9,3) = (9 8 7) / (1 2 3) = 84

组合数公式：c(m,n) = m! / (n! * (m - n)!)

解法1：python一行式！

1
2
3

class Solution:
    def uniquePaths(self, m, n):
        return int(math.factorial(m + n - 2) / math.factorial(m -1) / math.factorial(n-1))

解法2：

class Solution:
    def uniquePaths(self, m, n):
        if m <= 0 or n <= 0:
            return 0
        res = [0 for _ in range(0, n)]
        res[0] = 1
        for i in range(0, m):
            for j in range(1, n):
                res[j] += res[j-1]
        return res[n-1]

解法3：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]   
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

63. 不同路径 II

思路：加了障碍物。看了几种做法。

解法1：

class solution(object):
    def uniquePathsWithobstacles(self, obstacleGrid):
        m,n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        if obstacleGrid[0][0] == 0:
            dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[i][j] = 0
                else:
                    if i != 0:
                        dp[i][j] += dp[i - 1][j]
                    if j != 0:
                        dp[i][j] += dp[i][j - 1]
        return dp[m - 1][n - 1]

解法2：进行优化。利用Python语言特性来减少判断次数。我们遍历的方向是第一行从左到右，然后再第二行从左到右的方式进行的，这样如果把dp全部初始化成了0，那么当计算第一行的时候dp[-1][j]实际上就是最后一行的dp，也就是0.同样的，dp[i][-1]实际上是最后一列的dp，但是还没遍历到过，所以也是0.总之，虽然dp数组在计算第一行和第一列的时候用到了最后一行最后一列的dp数据，但是由于还没有遍历到，那么dp数组实际上是0，所以完全可以省去判断。这种方式对于C++和Java不能进行负数索引的不能用。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        if obstacleGrid[0][0] == 0:
            dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 0:
                    if i == j == 0:
                        continue
                    else:
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

322. 零钱兑换

思路：参考powcai 的解题代码。一题多解。可以用0/1背包,深度遍历(dfs),广度遍历(bfs)

有时间细化一下，各种解法。

解法1：动态规划

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        for i in range(1,amount + 1):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        return dp[-1] if dp[-1] != float('inf') else -1

解法2：深度遍历dfs

class Solution:
    def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
        from collections import defaultdict
        lookup = defaultdict(int)
        if amount < 1:
            return 0

        def helper(amount):
            if amount < 0:
                return -1
            if amount == 0:
                return 0
            if lookup[amount]:
                return lookup[amount]
            min_num = 2 ** 31 - 1
            for coin in coins:
                res = helper(amount - coin)
                # min_num = min(min_num,res + 1)
                if res >= 0 and res < min_num:
                    min_num = res + 1
                    lookup[amount] = min_num if min_num != 2 ** 31 - 1 else -1
                    return lookup[amount]

                return helper(amount)

解法3:广度遍历bfs

class Solution:
        def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
            
            #广度遍历bfs
            res = 0
            cur = [0]
            visited = set()
            coins.sort()
            while cur:
                next_time = []
                res += 1
                for tmp in cur:
                    for coin in coins:
                        sum_num = tmp + coin
                        if sum_num == amount:
                            return res
                        elif sum_num > amount:
                            break
                        elif sum_num < amount and sum_num not in visited:
                            next_time.append(sum_num)
                            visited.add(sum_num)
                cur = next_time
            return -1 if amount else 0

解法4：约束

class Solution:
       def coinChange(self, coins: 'List[int]', amount: 'int') -> 'int':
           self.res = float("inf")
           n = len(coins)
           if amount == 0:
               return 0
           coins.sort(reverse=True)
           if amount < coins[-1]:
               return -1
   
           def dfs(loc, remain, count):
               if remain == 0:
                   self.res = min(self.res, count)
               else:
                   for i in range(loc, n):
                       if coins[i] <= remain < coins[i] * (self.res - count):
                           dfs(i, remain - coins[i], count + 1)
   
           for i in range(n):
               dfs(i, amount, 0)
           return self.res if self.res != float("inf") else -1

Hard

32. 最长有效括号

分析：问题并不难。关键在于，运用一个列表暂存，一个列表计数。这个方式真的很不错。还有enumerate函数的运用，用取max方式获取最大子串。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        st, b = [], [0]*len(s)
        for i, val in enumerate(s):
            if val == '(':
                st.append(i)
            elif st:
                b[st.pop()], b[i] = 1, 1  #清空，记录

        c, mc = 0, 0
        for i in b:
            if i:
                c += 1
            else:
                mc = max(c, mc)  #排除单“括号”，中断后获取最大子串。
                c = 0

        return max(c, mc)

44. 通配符匹配

分析：虽然是hard难度，但理解题意。还是很简单的。关键点在于，“*”和“？”的适配情况。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[bool(0) for _ in range(n+1) ]for _ in range(m+1)]
        dp[0][0] = bool(1)
        for i in range(n):
            if dp[0][i] and p[i] == '*':
                dp[0][i+1] = bool(1)
       
        #动态规划        
        for i in range(m):
            for j in range(n):
                if p[j] == '*':
                    dp[i + 1][j + 1] = dp[i][j+1] or dp[i+1][j]
                elif p[j] == '?' or s[i] == p[j]:
                    dp[i+1][j+1] = dp[i][j]
        return dp[m][n]

174. 地下城游戏

分析：保证血量>=1.还是经典的动态规划做法，从后往前推。

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # 参考
        x, y = len(dungeon), len(dungeon[0])
        dp = [[0]*y for _ in range(x)]  # 能到达最后在这个位置的最小体力值,>=1
        dp[-1][-1] = max(1, 1-dungeon[-1][-1])
        for j in range(y-2, -1, -1):  # 最后一行
            dp[-1][j] = max(1, dp[-1][j+1]-dungeon[-1][j])
        for i in range(x-2, -1, -1):
            dp[i][-1] = max(1, dp[i+1][-1]-dungeon[i][-1])
        for j in range(y-2, -1, -1):  # 从右到左
            for i in range(x-2, -1, -1):  # 从下到上
                # 找这个位置下边或右边需要的较少体力值
                dp[i][j] = max(1, min(dp[i][j+1], dp[i+1][j])-dungeon[i][j])
        return dp[0][0]

403. 青蛙过河

分析：大概是这几道题中最有难度的一道了。国区的评论区竟然没有python3的答案。看别的程序思路有的用哈希表，有的用回溯法+贪心策略+剪枝。感觉一时半会没有好的思路，暂且存疑吧。等到修炼一段时间，再回顾。贴一下英文原站的答案。

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        '''
        let canCross(stones, i, k) be whether the frog can jump start from position i and frog's previou jump size is k. Then next jump can be either k - 1, k, or k + 1 so
        canCross(stones, i, k) = canCross(stones, i + k - 1, k - 1) or canCross(stones, i + k, k) or canCross(stones, i + k + 1, k + 1)
        if i + k - 1 or i + k or i + k + 1 be a stone position, otherwise canCross(stones, i, k) = False
        if i == stones[-1], the frog already sits on the last stone. Return True.
        '''
        self.memo = {}
        stonePos = set(stones)
        return self._canCross_helper(stones, 0, 0, stonePos)
        
    def _canCross_helper(self, stones:List[int], i: int, k:int, stonePos:set)->bool:
        if (i, k) in self.memo:
            return self.memo[(i, k)]
        ans = False
        if i == stones[-1]:
            ans = True
            self.memo[(i, k)] = ans
            return ans
        if k - 1 > 0:
            if i + k - 1 in stonePos:
                ans = ans or self._canCross_helper(stones, i + k - 1, k - 1, stonePos)
        if k > 0:
            if i + k in stonePos:
                ans = ans or self._canCross_helper(stones, i + k, k, stonePos)
        if i + k + 1 in stonePos:
            ans = ans or self._canCross_helper(stones, i + k + 1, k + 1, stonePos)
        self.memo[(i, k)] = ans
        return ans